Toying with the Collatz Conjecture

Introduction

I've spent a while now, on and off, toying around with the Collatz Conjecture. Here, I'll collect my observations, notes, and thoughts on the topic.

Some Background

The way the Collatz conjecture goes you choose a positive integer starting value and repeatedly apply one of two conditional operations.

If the current value is odd, then multiply by 3 and add 1.
Otherwise, if even divide the number by 2.

The conjecture states that for all positive integer starting values you will always reach 1 after applying this rule enough times.

To illustrate, let's start with 7: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...

This has ben exhaustively checked for starting values up to $2^{68}$ (at least at the time of writing), but a general proof that the conjecture is true has not yet been found (if one exists)...

Changing the Rules

While the Conjecture would normally have you start with some chosen positive integer, we can use inverse operations to start from 1 and try to prove that starting from 1 you can get to all positive integers. The operations when starting from 1 are as follows.

If the current value is equivalent to 4 mod 6, then subtract 1 and divide by 3.
Otherwise, double it.

To illustrate this, we'll start from 1 and go out an arbitrary distance.

1
2
4 – 1
8
16 ----------- 5
32             10 ------ 3
64 ------- 21  20        6
128        42  40 -- 13  12
256 -- 85  84  80    26  24

Stating the Obvious

There are a few "obvious" things to note:

The start of each branch is an odd number
- Because of this, it’s common to count the number of odds encountered before reaching 1 for a given starting integer
The “trunk” branch is every power of 2
Every branch is defined as the odd number at the beginning of the branch (n) times 2 to some power (k), $n 2^{k - 1}$ where $n, k \in ℤ^{+}$

Simple Patterns

`n` and $n + 1$

Looking closely, you might notice a few patterns. For example, 12 and 13, 20 and 21, 52 and 53, as well as 84 and 85 are on the same row (at least as I’ve written it out). As it turns out, this is not much of a surprise. Focusing on 12 and 13, they both share 10 as the closest common node. To get from 10 to 12 you subtract 1 and divide that difference by 3, then multiply by 2 twice. To get from 10 to 13 you multiply by 2 twice, then subtract 1 and divide that difference by 3. More generally it can be shown that for a starting value $n \in ℤ^{+}$ where $n mod 3 \equiv 1$ : $n = 3 q + 1$ $4 (\frac{3 q + 1 - 1}{3}) = 4 q$ $\frac{4 (3 q + 1) - 1}{3} = 4 q + 1$ But this is a special circumstance, if we could generally find n+1 for a given n then that would prove the conjecture.

Only Even Powers of 2 Branch off the “Trunk”

Looking at this small portion of the graph, it seems like only even powers of 2 have branches off the trunk. Indeed, it can be shown in general that for $k \in ℤ^{+}$ : $2^{2 k + 1} mod 3 \equiv 2$ $2^{2 k} mod 3 \equiv 1$ Thus, the trunk produces branches at $4^{k}$

Pascal's Triangle

Not really surprising once you think about it, but the coefficients of binomial expansion fall out of expressing $4^{n}$ in terms of powers of 3. This is of course because $4 = 3 + 1$ : $4^{n} = {(3 + 1)}^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 3^{n - k}$

Odds Directly Branching from the "Trunk"

Focusing in on the odds directly connected to the "trunk" branch (the branch containing all powers of 2), there's a pattern: $1, 5, 21, 85, \dots$ $1 = 1$ $5 = 1 + 4$ $21 = 1 + 4 + 16$ $85 = 1 + 4 + 16 + 64$ It can be shown given $4^{n}$ the beginning odd value for the start of the branch off the trunk is of form: $\sum_{i = 0}^{n - 1} 4^{i}$

Generally Expressing the Numbers in Each Branch Level from the Trunk

Let’s look at how we arrive at the above result (the general expression of odd values 1 level away from the trunk). To do this we'll show that $a^{n} = 1 + (a - 1) \sum_{i = 0}^{n - 1} a^{i}$ for $a, n \in ℤ^{+}$ .

$\begin{aligned} 1 + (a - 1) \sum_{i = 0}^{n - 1} a^{i} & = 1 + a (\sum_{i = 0}^{n - 1} a^{i}) - \sum_{i = 0}^{n - 1} a^{i} \\ = 1 + \sum_{i = 0}^{n - 1} a^{i + 1} - \sum_{i = 0}^{n - 1} a^{i} \\ = 1 + \sum_{i = 1}^{n} a^{i} - \sum_{i = 1}^{n - 1} a^{i} - 1 \\ = 1 + a^{n} + \sum_{i = 1}^{n - 1} a^{i} - \sum_{i = 1}^{n - 1} a^{i} - 1 \\ = a^{n} \end{aligned}$

This is quite handy because that means we can now express $4^{n}$ as $1 + 3 \sum_{i = 0}^{n - 1} 4^{i}$ . Now to get to the first branch we subtract $1$ and divide the difference by 3 to find that the odds beginning the first branch are sums of sequential powers of $4$ : $\frac{(1 + 3 \sum_{i = 0}^{n - 1} 4^{i}) - 1}{3} = \sum_{i = 0}^{n - 1} 4^{i}$

Handily, we are still left with an expression comprised entirely of terms $4$ to some power, so we can apply the same rule to each of these terms except when $i = 0$ : $\sum_{i = 0}^{n - 1} 4^{i} = 1 + \sum_{i_{1} = 1}^{n - 1} (1 + 3 \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) = n + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}$

Now, the problem is we need to know the value of $n mod 3$ . Fortunately, there are only 3 options to explore (or really just 2 as we'll see). Let's assume each possible value and continue.

$Let n mod 3 \equiv 0, n = 3 n_{1}$ $n + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}} = 3 n_{1} + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}$

Now to find all even values we have $2^{k_{1}} (3 n_{1} + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}); k_{i} \in ℤ^{+}$

Because $3 n_{1} + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}} mod 3 \equiv 0$ , there isn't any power of 2 that can make this equivalent to 4 modulo 6.

$Let n mod 3 \equiv 1, n = 3 n_{1} + 1$ $n + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}} = 3 n_{1} + 1 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}$

Now to find all even values we have $2^{k_{1}} (3 n_{1} + 1 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}); k_{i} \in ℤ^{+}$

Because $3 n_{1} + 1 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}} mod 3 \equiv 1$ , every $2^{2 k_{1}} (3 n_{1} + 1 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) mod 6 \equiv 4$ . This means that we can branch of at those points. So then what do the values on which we land (on branch level 2) look like from this starting point?

$\begin{array}{l} \frac{4^{k_{1}} (3 n_{1} + 1 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) - 1}{3} \\ = \frac{3 (4^{k_{1}} n_{1}) + 4^{k_{1}} + 3 (4^{k_{1}} \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) - 1}{3} \\ = \frac{3 (4^{k_{1}} n_{1}) + 1 + 3 \sum_{j_{1} = 0}^{k_{1} - 1} 4^{j_{1}} + 3 (4^{k_{1}} \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) - 1}{3} \\ = 4^{k_{1}} n_{1} + \sum_{j_{1} = 0}^{k_{1} - 1} 4^{j_{1}} + (4^{k_{1}} \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) \end{array}$

This expresses all odd values that begin the second branch under the condition that $n mod 3 \equiv 1$ .

$Let n mod 3 \equiv 2, n = 3 n_{1} + 2$ $n + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}} = 3 n_{1} + 2 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}$

Now to find all even values we have $2^{k_{1}} (3 n_{1} + 2 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}); k_{i} \in ℤ^{+}$

Because $3 n_{1} + 2 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}} mod 3 \equiv 2$ , every $2^{2 (k_{1} - 1) + 1} (3 n_{1} + 2 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) mod 6 \equiv 4$ . This means that we can branch of at those points. So then what do the values on which we land (on branch level 2) look like from this starting point?

$\begin{array}{l} \frac{2 \cdot 4^{k_{1} - 1} (3 n_{1} + 2 + 3 \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) - 1}{3} \\ = \frac{3 (2 \cdot 4^{k_{1} - 1} n_{1}) + 4^{k_{1}} + 3 (2 \cdot 4^{k_{1} - 1} \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) - 1}{3} \\ = \frac{3 (2 \cdot 4^{k_{1} - 1} n_{1}) + 1 + 3 \sum_{j_{1} = 0}^{k_{1} - 1} 4^{j_{1}} + 3 (2 \cdot 4^{k_{1} - 1} \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) - 1}{3} \\ = 2 \cdot 4^{k_{1} - 1} n_{1} + \sum_{j_{1} = 0}^{k_{1} - 1} 4^{j_{1}} + (2 \cdot 4^{k_{1} - 1} \sum_{i_{1} = 1}^{n - 1} \sum_{i_{2} = 0}^{i_{1} - 1} 4^{i_{2}}) \end{array}$

This expresses all odd values that begin the second branch under the condition that $n mod 3 \equiv 2$ .

As shown above, branch level 2 has two forms. We can continue down this same path to express the form for branch level 3 and presumably the nth branch. However, it appears that each branch will increase the number of forms to represent its values so this approach may not be useful unless an obvious pattern falls out of it or it somehow makes obvious a counter example.

Consequential Paths

What I'm calling consequential paths are paths to traverse the graph of numbers resulting from the permitted operations that are otherwise not the permitted operations themselves.

An important thing to note is that n can be expressed as a nested set of operations of multiply by 3 and adding either 0, 1, or 2. The point of this may become clear as we proceed.